﻿using System;
using System.Collections.Generic;

public class PriorityQueue<T>
{
    private T[] elements;

    private int size;
    public int Size { get => size; }

    private int capacity;

    private Func<T, T, bool> handler;

    /// <summary>扩容系数</summary>
    private float expansionCoefficient = 2f;
    public float ExpansionCoefficient
    {
        get => expansionCoefficient;
        set
        {
            if (value <= 1)
                throw new Exception("PriorityQueue: expansionCoefficient should be bigger than 1");
            expansionCoefficient = value;
        }
    }

    /// <param name="_handler"> 若为true，则a优先出列 </param>
    /// <param name="_capacity"> 初始容量 </param>
    public PriorityQueue(Func<T, T, bool> _handler, int _capacity = 8)
    {
        if (_capacity <= 0)
            throw new Exception("PriorityQueue: capacity must be bigger than 0");
        this.handler = _handler;
        this.capacity = _capacity;

        elements = new T[capacity];
    }

    public bool IsEmpty()
    {
        return size == 0;
    }

    public T Top()
    {
        if (IsEmpty())
            throw new Exception("PriorityQueue: try Top() but it's empty");
        return elements[0];
    }

    public void Pop()
    {
        if (IsEmpty())
            throw new Exception("PriorityQueue: try Pop() but it's empty");

        elements[0] = elements[--size];

        int cur = 0;

        while (true)
        {
            int childa = cur * 2 + 1;
            int childb = cur * 2 + 2;

            if (childa >= size) break;

            int done = childa;

            if (childb < size)
            {
                if (!handler(elements[childa], elements[childb]))
                {
                    done = childb;
                }
            }

            if (!handler(elements[cur], elements[done]))
            {
                T temp = elements[cur];
                elements[cur] = elements[done];
                elements[done] = temp;

                cur = done;
            }
            else break;
        }
    }


    public void Push(T item)
    {
        if (size == capacity)
        {
            //避免计算的新容量小于等于原容量
            int _capacity = (int)(expansionCoefficient * capacity);
            Resize(_capacity <= capacity ? capacity + 1 : _capacity);
        }

        elements[size++] = item;

        int cur = size - 1;

        while (cur != 0)
        {
            int father = (cur - 1) / 2;

            if (!handler(elements[father], elements[cur]))
            {
                T temp = elements[cur];
                elements[cur] = elements[father];
                elements[father] = temp;

                cur = father;
            }
            else break;
        }
    }

    /*
	 * 将可迭代的容器中的元素逐个压入队列
	 */
    public void Push(IEnumerable<T> collection)
    {
        foreach (T item in collection)
        {
            Push(item);
        }
    }

    /* 
	 * 重新设置容量，如果新设置的容量不够容纳原本的数据，溢出的部分会丢失
	 */
    public void Resize(int _capacity)
    {
        if (_capacity <= 0)
            throw new Exception("PriorityQueue: capacity must be bigger than 0");

        T[] _bucket = new T[_capacity];
        for (int i = 0; i < this.size && i < _capacity; ++i)
        {
            _bucket[i] = this.elements[i];
        }
        this.elements = _bucket;
        this.capacity = _capacity;
        this.size = size > capacity ? capacity : size;
    }
}
